<!-- HTML header for doxygen 1.8.6-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<title>OpenCV: Hough Line Transform</title>
<link href="../../opencv.ico" rel="shortcut icon" type="image/x-icon" />
<link href="../../tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../jquery.js"></script>
<script type="text/javascript" src="../../dynsections.js"></script>
<script type="text/javascript" src="../../tutorial-utils.js"></script>
<link href="../../search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../search/searchdata.js"></script>
<script type="text/javascript" src="../../search/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
    jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
  TeX: {
      Macros: {
          matTT: [ "\\[ \\left|\\begin{array}{ccc} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{array}\\right| \\]", 9],
          fork: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ \\end{array} \\right.", 4],
          forkthree: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ \\end{array} \\right.", 6],
          forkfour: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ #7 & \\mbox{#8}\\\\ \\end{array} \\right.", 8],
          vecthree: ["\\begin{bmatrix} #1\\\\ #2\\\\ #3 \\end{bmatrix}", 3],
          vecthreethree: ["\\begin{bmatrix} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{bmatrix}", 9],
          cameramatrix: ["#1 = \\begin{bmatrix} f_x & 0 & c_x\\\\ 0 & f_y & c_y\\\\ 0 & 0 & 1 \\end{bmatrix}", 1],
          distcoeffs: ["(k_1, k_2, p_1, p_2[, k_3[, k_4, k_5, k_6 [, s_1, s_2, s_3, s_4[, \\tau_x, \\tau_y]]]]) \\text{ of 4, 5, 8, 12 or 14 elements}"],
          distcoeffsfisheye: ["(k_1, k_2, k_3, k_4)"],
          hdotsfor: ["\\dots", 1],
          mathbbm: ["\\mathbb{#1}", 1],
          bordermatrix: ["\\matrix{#1}", 1]
      }
  }
}
);
//]]>
</script><script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js"></script>
<link href="../../doxygen.css" rel="stylesheet" type="text/css" />
<link href="../../stylesheet.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<!--#include virtual="/google-search.html"-->
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="../../opencv-logo-small.png"/></td>
  <td style="padding-left: 0.5em;">
   <div id="projectname">OpenCV
   &#160;<span id="projectnumber">4.5.2</span>
   </div>
   <div id="projectbrief">Open Source Computer Vision</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../../search",false,'Search');
</script>
<script type="text/javascript" src="../../menudata.js"></script>
<script type="text/javascript" src="../../menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('../../',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="../../d6/d00/tutorial_py_root.html">OpenCV-Python Tutorials</a></li><li class="navelem"><a class="el" href="../../d2/d96/tutorial_py_table_of_contents_imgproc.html">Image Processing in OpenCV</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">Hough Line Transform </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h2>Goal </h2>
<p>In this chapter,</p><ul>
<li>We will understand the concept of the Hough Transform.</li>
<li>We will see how to use it to detect lines in an image.</li>
<li>We will see the following functions: <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#ga46b4e588934f6c8dfd509cc6e0e4545a" title="Finds lines in a binary image using the standard Hough transform. ">cv.HoughLines()</a></b>, <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#ga8618180a5948286384e3b7ca02f6feeb" title="Finds line segments in a binary image using the probabilistic Hough transform. ">cv.HoughLinesP()</a></b></li>
</ul>
<h2>Theory </h2>
<p>The Hough Transform is a popular technique to detect any shape, if you can represent that shape in a mathematical form. It can detect the shape even if it is broken or distorted a little bit. We will see how it works for a line.</p>
<p>A line can be represented as \(y = mx+c\) or in a parametric form, as \(\rho = x \cos \theta + y \sin \theta\) where \(\rho\) is the perpendicular distance from the origin to the line, and \(\theta\) is the angle formed by this perpendicular line and the horizontal axis measured in counter-clockwise (That direction varies on how you represent the coordinate system. This representation is used in OpenCV). Check the image below:</p>
<div class="image">
<object type="image/svg+xml" data="../../houghlines1.svg">houghlines1.svg</object>
<div class="caption">
image</div></div>
<p> So if the line is passing below the origin, it will have a positive rho and an angle less than 180. If it is going above the origin, instead of taking an angle greater than 180, the angle is taken less than 180, and rho is taken negative. Any vertical line will have 0 degree and horizontal lines will have 90 degree.</p>
<p>Now let's see how the Hough Transform works for lines. Any line can be represented in these two terms, \((\rho, \theta)\). So first it creates a 2D array or accumulator (to hold the values of the two parameters) and it is set to 0 initially. Let rows denote the \(\rho\) and columns denote the \(\theta\). Size of array depends on the accuracy you need. Suppose you want the accuracy of angles to be 1 degree, you will need 180 columns. For \(\rho\), the maximum distance possible is the diagonal length of the image. So taking one pixel accuracy, the number of rows can be the diagonal length of the image.</p>
<p>Consider a 100x100 image with a horizontal line at the middle. Take the first point of the line. You know its (x,y) values. Now in the line equation, put the values \(\theta = 0,1,2,....,180\) and check the \(\rho\) you get. For every \((\rho, \theta)\) pair, you increment value by one in our accumulator in its corresponding \((\rho, \theta)\) cells. So now in accumulator, the cell (50,90) = 1 along with some other cells.</p>
<p>Now take the second point on the line. Do the same as above. Increment the values in the cells corresponding to <code>(rho, theta)</code> you got. This time, the cell (50,90) = 2. What you actually do is voting the \((\rho, \theta)\) values. You continue this process for every point on the line. At each point, the cell (50,90) will be incremented or voted up, while other cells may or may not be voted up. This way, at the end, the cell (50,90) will have maximum votes. So if you search the accumulator for maximum votes, you get the value (50,90) which says, there is a line in this image at a distance 50 from the origin and at angle 90 degrees. It is well shown in the below animation (Image Courtesy: <a href="http://homepages.inf.ed.ac.uk/amos/hough.html">Amos Storkey</a> )</p>
<div class="image">
<img src="../../houghlinesdemo.gif" alt="houghlinesdemo.gif"/>
</div>
<p>This is how hough transform works for lines. It is simple, and may be you can implement it using Numpy on your own. Below is an image which shows the accumulator. Bright spots at some locations denote they are the parameters of possible lines in the image. (Image courtesy: <a href="http://en.wikipedia.org/wiki/Hough_transform">Wikipedia</a> )</p>
<div class="image">
<img src="../../houghlines2.jpg" alt="houghlines2.jpg"/>
</div>
<h1>Hough Transform in OpenCV </h1>
<p>Everything explained above is encapsulated in the OpenCV function, <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#ga46b4e588934f6c8dfd509cc6e0e4545a" title="Finds lines in a binary image using the standard Hough transform. ">cv.HoughLines()</a></b>. It simply returns an array of :math:(rho, theta)` values. \(\rho\) is measured in pixels and \(\theta\) is measured in radians. First parameter, Input image should be a binary image, so apply threshold or use canny edge detection before applying hough transform. Second and third parameters are \(\rho\) and \(\theta\) accuracies respectively. Fourth argument is the threshold, which means the minimum vote it should get to be considered as a line. Remember, number of votes depends upon the number of points on the line. So it represents the minimum length of line that should be detected. </p><div class="fragment"><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"></div><div class="line">img = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<a class="code" href="../../d6/dba/group__core__utils__samples.html#ga3a33b00033b46c698ff6340d95569c13">cv.samples.findFile</a>(<span class="stringliteral">&#39;sudoku.png&#39;</span>))</div><div class="line">gray = <a class="code" href="../../d8/d01/group__imgproc__color__conversions.html#ga397ae87e1288a81d2363b61574eb8cab">cv.cvtColor</a>(img,cv.COLOR_BGR2GRAY)</div><div class="line">edges = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#ga2a671611e104c093843d7b7fc46d24af">cv.Canny</a>(gray,50,150,apertureSize = 3)</div><div class="line"></div><div class="line">lines = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#ga46b4e588934f6c8dfd509cc6e0e4545a">cv.HoughLines</a>(edges,1,np.pi/180,200)</div><div class="line"><span class="keywordflow">for</span> line <span class="keywordflow">in</span> lines:</div><div class="line">    rho,theta = line[0]</div><div class="line">    a = np.cos(theta)</div><div class="line">    b = np.sin(theta)</div><div class="line">    x0 = a*rho</div><div class="line">    y0 = b*rho</div><div class="line">    x1 = int(x0 + 1000*(-b))</div><div class="line">    y1 = int(y0 + 1000*(a))</div><div class="line">    x2 = int(x0 - 1000*(-b))</div><div class="line">    y2 = int(y0 - 1000*(a))</div><div class="line"></div><div class="line">    <a class="code" href="../../d6/d6e/group__imgproc__draw.html#ga7078a9fae8c7e7d13d24dac2520ae4a2">cv.line</a>(img,(x1,y1),(x2,y2),(0,0,255),2)</div><div class="line"></div><div class="line"><a class="code" href="../../d4/da8/group__imgcodecs.html#gabbc7ef1aa2edfaa87772f1202d67e0ce">cv.imwrite</a>(<span class="stringliteral">&#39;houghlines3.jpg&#39;</span>,img)</div></div><!-- fragment --><p> Check the results below:</p>
<div class="image">
<img src="../../houghlines3.jpg" alt="houghlines3.jpg"/>
<div class="caption">
image</div></div>
 <h2>Probabilistic Hough Transform </h2>
<p>In the hough transform, you can see that even for a line with two arguments, it takes a lot of computation. Probabilistic Hough Transform is an optimization of the Hough Transform we saw. It doesn't take all the points into consideration. Instead, it takes only a random subset of points which is sufficient for line detection. We just have to decrease the threshold. See image below which compares Hough Transform and Probabilistic Hough Transform in Hough space. (Image Courtesy : <a href="http://phdfb1.free.fr/robot/mscthesis/node14.html">Franck Bettinger's home page</a> )</p>
<div class="image">
<img src="../../houghlines4.png" alt="houghlines4.png"/>
<div class="caption">
image</div></div>
<p> OpenCV implementation is based on Robust Detection of Lines Using the Progressive Probabilistic Hough Transform by Matas, J. and Galambos, C. and Kittler, J.V. <a class="el" href="../../d0/de3/citelist.html#CITEREF_Matas00">[165]</a>. The function used is <b><a class="el" href="../../dd/d1a/group__imgproc__feature.html#ga8618180a5948286384e3b7ca02f6feeb" title="Finds line segments in a binary image using the probabilistic Hough transform. ">cv.HoughLinesP()</a></b>. It has two new arguments.</p><ul>
<li><b>minLineLength</b> - Minimum length of line. Line segments shorter than this are rejected.</li>
<li><b>maxLineGap</b> - Maximum allowed gap between line segments to treat them as a single line.</li>
</ul>
<p>Best thing is that, it directly returns the two endpoints of lines. In previous case, you got only the parameters of lines, and you had to find all the points. Here, everything is direct and simple. </p><div class="fragment"><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"></div><div class="line">img = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<a class="code" href="../../d6/dba/group__core__utils__samples.html#ga3a33b00033b46c698ff6340d95569c13">cv.samples.findFile</a>(<span class="stringliteral">&#39;sudoku.png&#39;</span>))</div><div class="line">gray = <a class="code" href="../../d8/d01/group__imgproc__color__conversions.html#ga397ae87e1288a81d2363b61574eb8cab">cv.cvtColor</a>(img,cv.COLOR_BGR2GRAY)</div><div class="line">edges = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#ga2a671611e104c093843d7b7fc46d24af">cv.Canny</a>(gray,50,150,apertureSize = 3)</div><div class="line">lines = <a class="code" href="../../dd/d1a/group__imgproc__feature.html#ga8618180a5948286384e3b7ca02f6feeb">cv.HoughLinesP</a>(edges,1,np.pi/180,100,minLineLength=100,maxLineGap=10)</div><div class="line"><span class="keywordflow">for</span> line <span class="keywordflow">in</span> lines:</div><div class="line">    x1,y1,x2,y2 = line[0]</div><div class="line">    <a class="code" href="../../d6/d6e/group__imgproc__draw.html#ga7078a9fae8c7e7d13d24dac2520ae4a2">cv.line</a>(img,(x1,y1),(x2,y2),(0,255,0),2)</div><div class="line"></div><div class="line"><a class="code" href="../../d4/da8/group__imgcodecs.html#gabbc7ef1aa2edfaa87772f1202d67e0ce">cv.imwrite</a>(<span class="stringliteral">&#39;houghlines5.jpg&#39;</span>,img)</div></div><!-- fragment --><p> See the results below:</p>
<div class="image">
<img src="../../houghlines5.jpg" alt="houghlines5.jpg"/>
<div class="caption">
image</div></div>
 <h2>Additional Resources </h2>
<ol type="1">
<li><a href="http://en.wikipedia.org/wiki/Hough_transform">Hough Transform on Wikipedia</a></li>
</ol>
<h2>Exercises </h2>
</div></div><!-- contents -->
<!-- HTML footer for doxygen 1.8.6-->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Fri Apr 2 2021 11:36:37 for OpenCV by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="../../doxygen.png" alt="doxygen"/>
</a> 1.8.13
</small></address>
<script type="text/javascript">
//<![CDATA[
addTutorialsButtons();
//]]>
</script>
</body>
</html>
